package leetcode;

import java.util.ArrayList;

/**
 * @Project : AlgorithmLearning
 * @Package : Leetcode
 * @File : Q0042.java
 * @Author : WangRuoyu
 * @Date 2023/11/4 21:58
 */


public class Q0042 {

    public int trap(int[] height) {
        int res = 0;

        ArrayList<Integer> big = new ArrayList<>();
        for (int i = 0; i < height.length; i++) {
            while (!big.isEmpty() && height[big.get(big.size() - 1)] < height[i]) {
                if (big.size() > 1) {
                    int j = big.get(big.size() - 2);
                    res += (Math.min(height[j], height[i]) - height[big.get(big.size() - 1)]) * (i - j - 1);
                }
                big.remove(big.size() - 1);
            }
            big.add(i);
        }

        return res;
    }

//    public int trap(int[] height) {
//        int[] st = new int[height.length];
//        int cnt = 0;
//        int res = 0;
//
//        for (int i = 0; i < height.length; i++) {
//            while (cnt > 0 && height[st[cnt - 1]] < height[i]) {
//                if (cnt > 1) {
//                    int j = st[cnt - 2];
//                    res += (Math.min(height[j], height[i]) - height[st[cnt - 1]]) * (i - j - 1);
//                }
//                cnt--;
//            }
//            st[cnt++] = i;
//        }
//        return res;
//    }

    public static void main(String[] args) {
        Q0042 sl = new Q0042();
        int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        System.out.println(sl.trap(height));
    }
}